1. A Heap is a complete tree (All levels are completely filled except possibly the last level and the last level has all keys as left as possible).


2. A Heap is either Min Heap or Max Heap. In a Min-Heap, the key at root must be minimum among all keys present in the Binary Heap. The same property must be recursively true for all nodes in the Tree. Max Heap is similar to MinHeap.
   

Representing Binary Heaps

• The root element will be at Arr[0].
• Below table shows indexes of other nodes for the i^th node, i.e., Arr[i]:
  

  Arr[(i-1)/2]	Returns the parent node
  Arr[(2*i)+1]	Returns the left child node
  Arr[(2*i)+2]	Returns the right child node

Heapifying an Element

• Step 1: Swap the node 4 with the maximum of its childrens i.e., max(10, 3).
  
  
• Step 2: Again the node 4 does not follow the heap property. Swap the node 4 with the maximum of its new childrens i.e., max(5, 1).
  
  
• The Node 4 is now heapified successfully and placed at it's correct position.
  

Deletion in Heap

Given a Binary Heap and an element present in the given Heap. The task is to delete an element from this Heap.

• Replace the root or element to be deleted by the last element.
• Delete the last element from the Heap.
• Since, the last element is now placed at the position of the root node. So, it may not follow the heap property. Therefore, heapify the last node placed at the position of root.

Suppose the Heap is a Max-Heap as:


The element to be deleted is root, i.e. 10.

Process:
The last element is 4.

Step 1: Replace the last element with root, and delete it.


Step 2: Heapify root.
Final Heap:
   

5 4 3 2

• Replace the element to be deleted with minus Infinite (INT_MIN in C++ and Integer.MIN_VALUE in Java)
• Keep swapping the minus infinite value with parent until it reaches root
• Now delete the root using process discussed above

Let us try deleting 30 from below Min Heap


We replace 30 with -INF


We move -INF to root by swapping with parent
nodes one by one


Now Delete Root (We first replace it with last node
then call heapify)
   

Insertion in Heaps

Given a Binary Heap and a new element to be added to this Heap. The task is to insert the new element to the Heap maintaining the properties of Heap.

• First increase the heap size by 1, so that it can store the new element.
• Insert the new element at the end of the Heap.
• This newly inserted element may distort the properties of Heap for its parents. So, in order to keep the properties of Heap, heapify this newly inserted element following a bottom-up approach.

Suppose the Heap is a Max-Heap as:


The new element to be inserted is 15.

Process:
Step 1: Insert the new element at the end.


Step 2: Heapify the new element following bottom-up 
        approach.
-> 15 is less than its parent 3, swap them.


-> 15 is again less than its parent 10, swap them.


Therefore, the final heap after insertion is:
-> 15 is less than its parent 3, swap them.

15 5 10 2 4 3

Given N elements. The task is to build a Binary Heap from the given array. The heap can be either Max Heap or Min Heap.

Root is at index 0 in array.
Left child of i-th node is at (2*i + 1)th index.
Left child of i-th node is at (2*i + 2)th index.
Parent of i-th node is at (i-1)/2 index.

Last non-leaf node = parent of last-node.
or, Last non-leaf node = parent of node at (n-1)th index.
or, Last non-leaf node = Node at index ((n-1) - 1)/2.
                       = (n - 2)/2.

Array = {1, 3, 5, 4, 6, 13, 10, 9, 8, 15, 17}

Corresponding Complete Binary Tree is:


The task to build a Max-Heap from above array.

Total Nodes = 11.
Last Non-leaf node index = (11/2) - 1 = 4.
Therefore, last non-leaf node = 6.

To build the heap, heapify only the nodes:
[1, 3, 5, 4, 6] in reverse order.

Heapify 6: Swap 6 and 17.


Heapify 4: Swap 4 and 9.


Heapify 5: Swap 13 and 5.


Heapify 3: First Swap 3 and 17, again swap 3 and 15.


Heapify 1: First Swap 1 and 17, again swap 1 and 15, 
           finally swap 1 and 6.

Array representation of Heap is:
17 15 13 9 6 5 10 4 8 3 1

Heaps in C++

• For implementing Max Heap:
  

  priority_queue< type_of_data > name_of_heap;
  

• For implementing Min Heap:
  

  priority_queue< type, vector<type>, greater<type> > name_of_heap;
  

• priority_queue::empty(): The empty() function returns whether the queue is empty.
• priority_queue::size(): The size() function returns the size of the queue.
• priority_queue::top(): This function returns a reference to the top most element of the queue.
• priority_queue::push(): The push(g) function adds the element ‘g’ at the end of the queue.
• priority_queue::pop(): The pop() function deletes the first element of the queue.
• priority_queue::swap(): This function is used to swap the contents of one priority queue with another priority queue of same type and size.

Element at top of Max Heap at every step:
30 20 10 5 1 

Element at top of Min Heap at every step:
1 5 10 20 30

Heaps in Java

• Implementing Max Heap:
  

  Queue<Integer> max_heap = new PriorityQueue<>(                         
                                   Collections.reverseOrder());
  

• Implementing Min Heap:
  

  Queue<Integer> min_heap = new PriorityQueue<>(); 
  

• boolean add(E element): This method inserts the specified element into this priority queue.
• public remove(): This method removes a single instance of the specified element from this queue, if it is present.
• public poll(): This method retrieves and removes the head of this queue, or returns null if this queue is empty.
• public peek(): This method retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.
• void clear(): This method is used to remove all of the contents of the priority queue.
• int size(): The method is used to return the number of elements present in the set.

Some error occured or ide is down,please try again

Problem #1 : Heap Sort - Ascending Order

1. Build a max heap from the input data.
2. At this point, the largest item is stored at the root of the heap. Replace it with the last item of the heap followed by reducing the size of heap by 1. Finally, heapify the root of tree.
3. Repeat above steps while size of heap is greater than 1.

// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify( arr[], n, i)
{
    largest = i // Initialize largest as root
    l = 2*i + 1 // left = 2*i + 1
    r = 2*i + 2 // right = 2*i + 2

    // If left child is larger than root
    if (l < n && arr[l] > arr[largest])
        largest = l

    // If right child is larger than largest so far
    if (r < n && arr[r] > arr[largest])
        largest = r

    // If largest is not root
    if (largest != i)
    {
        swap(arr[i], arr[largest])

        // Recursively heapify the affected sub-tree
        heapify(arr, n, largest)
    }
}

// main function to do heap sort
void heapSort( arr[], n)
{
    // Build heap (rearrange array)
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i)

    // One by one extract an element from heap
    for (int i=n-1; i>=0; i--)
    {
        // Move current root to end
        swap(arr[0], arr[i])

        // call max heapify on the reduced heap
        heapify(arr, i, 0)
    }
}

Problem #2 : K’th Smallest/Largest Element in Unsorted Array

void MinHeap( a[], size) 
{ 
    heap_size = size
    harr = a // store address of array 
    int i = (heap_size - 1)/2
    while (i >= 0) 
    { 
        MinHeapify(i)
        i--
    } 
} 
  
// Method to remove minimum element (or root) from min heap 
int extractMin() 
{ 
    if (heap_size == 0) 
        return INT_MAX
  
    // Store the minimum vakue. 
    int root = harr[0]
  
    // If there are more than 1 items, move the last item to root 
    // and call heapify. 
    if (heap_size > 1) 
    { 
        harr[0] = harr[heap_size-1]
        MinHeapify(0)
    } 
    heap_size--
  
    return root
} 
// A recursive method to heapify a subtree with root at given index 
// This method assumes that the subtrees are already heapified 
void MinHeapify(int i) 
{ 
    int l = left(i)
    int r = right(i)
    int smallest = i; 
    if (l < heap_size && harr[l] < harr[i]) 
        smallest = l
    if (r < heap_size && harr[r] < harr[smallest]) 
        smallest = r
    if (smallest != i) 
    { 
        swap(& harr[i], & harr[smallest])
        MinHeapify(smallest)
    } 
}  
// Returns Minimum Element 
int getMin() 
{
    return harr[0]
}
// Function to return k'th smallest element in a given array 
int kthSmallest( arr[], n, k) 
{ 
    // Build a heap of n elements: O(n) time 
    MinHeap(arr, n)
  
    // Do extract min (k-1) times 
    for (int i=0; i < k-1; i++) 
        extractMin()
  
    // Return root 
    return getMin()
} 

Problem #3 : Median of Stream of Running Integers using STL

What is Median?

Input: 5 10 15
Output: 5
        7.5
        10

1. Create two heaps. One max heap to maintain elements of lower half and one min heap to maintain elements of higher half at any point of time..
2. Take initial value of median as 0.
3. For every newly read element, insert it into either max heap or min heap and calulate the median based on the following conditions:
   
   • If the size of max heap is greater than size of min heap and the element is less than previous median then pop the top element from max heap and insert into min heap and insert the new element to max heap else insert the new element to min heap. Calculate the new median as average of top of elements of both max and min heap.
     
   • If the size of max heap is less than size of min heap and the element is greater than previous median then pop the top element from min heap and insert into max heap and insert the new element to min heap else insert the new element to max heap. Calculate the new median as average of top of elements of both max and min heap.
     
   • If the size of both heaps are same. Then check if current is less than previous median or not. If the current element is less than previous median then insert it to max heap and new median will be equal to top element of max heap. If the current element is greater than previous median then insert it to min heap and new median will be equal to top element of min heap.
     

// function to calculate median of stream
void printMedian(double arr[], int n)
{
    // max heap to store the smaller half elements
    priority_queue s;
 
    // min heap to store the greater half elements
    priority_queue,greater > g;
 
    double med = arr[0];
    s.push(arr[0]);
 
    print(med)
 
    // reading elements of stream one by one
    /*  At any time we try to make heaps balanced and
        their sizes differ by at-most 1. If heaps are
        balanced,then we declare median as average of
        min_heap_right.top() and max_heap_left.top()
        If heaps are unbalanced,then median is defined
        as the top element of heap of larger size  */
    for (int i=1; i < n; i++)
    {
        double x = arr[i];
 
        // case1(left side heap has more elements)
        if (s.size() > g.size())
        {
            if (x < med)
            {
                g.push(s.top());
                s.pop();
                s.push(x);
            }
            else
                g.push(x);
 
            med = (s.top() + g.top())/2.0;
        }
 
        // case2(both heaps are balanced)
        else if (s.size()==g.size())
        {
            if (x < med)
            {
                s.push(x);
                med = (double)s.top();
            }
            else
            {
                g.push(x);
                med = (double)g.top();
            }
        }
 
        // case3(right side heap has more elements)
        else
        {
            if (x > med)
            {
                s.push(g.top());
                g.pop();
                g.push(x);
            }
            else
                s.push(x);
 
            med = (s.top() + g.top())/2.0;
        }
 
        print(med)
    }
}